#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* cur1 = head1, * cur2 = head2;
        ListNode* newhead, * tail;
        newhead = tail = new ListNode();
        while (cur1 && cur2) {
            if (cur1->val < cur2->val) {
                tail->next = cur1;
                tail = cur1;
                cur1 = cur1->next;
            }
            else {
                tail->next = cur2;
                tail = cur2;
                cur2 = cur2->next;
            }
        }
        if (cur1) {
            tail->next = cur1;
        }
        if (cur2) {
            tail->next = cur2;
        }
        return newhead->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        int flag = 0;
        for (auto e : lists)
        {
            if (e) flag = 1;
        }
        if (flag == 0) return nullptr;

        ListNode* newhead;
        newhead = new ListNode();
        for (int i = 0; i < lists.size(); i++)
        {
            newhead->next = merge(newhead->next, lists[i]);
        }
        return newhead->next;
    }
};